#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
typedef struct TreeNode {
    int value;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 定义栈节点结构
typedef struct StackNode {
    TreeNode* treeNode;
    struct StackNode* next;
} StackNode;

// 创建一个新的栈节点
StackNode* createStackNode(TreeNode* node) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    newNode->treeNode = node;
    newNode->next = NULL;
    return newNode;
}

// 入栈操作
void push(StackNode** top, TreeNode* node) {
    StackNode* newNode = createStackNode(node);
    newNode->next = *top;
    *top = newNode;
}

// 出栈操作
TreeNode* pop(StackNode** top) {
    if (*top == NULL) {
        return NULL;
    }
    StackNode* temp = *top;
    TreeNode* node = temp->treeNode;
    *top = (*top)->next;
    free(temp);
    return node;
}

// 判断栈是否为空
int isStackEmpty(StackNode* top) {
    return top == NULL;
}

// 层次遍历二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    StackNode* stack1 = NULL; // 用于存储当前层的节点
    StackNode* stack2 = NULL; // 用于存储下一层的节点

    // 初始化，根节点入栈
    push(&stack1, root);

    while (!isStackEmpty(stack1)) {
        // 处理当前层的节点
        while (!isStackEmpty(stack1)) {
            TreeNode* current = pop(&stack1);
            printf("%d ", current->value);

            // 将当前节点的左右子节点推入 stack2
            if (current->left != NULL) {
                push(&stack2, current->left);
            }
            if (current->right != NULL) {
                push(&stack2, current->right);
            }
        }

        printf("\n");

        // 交换 stack1 和 stack2
        StackNode* temp = stack1;
        stack1 = stack2;
        stack2 = temp;
    }
}

// 创建一个新的树节点
TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    newNode->value = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 主函数
int main() {
    // 创建树的节点
    TreeNode* root = createNode(1);
    TreeNode* node2 = createNode(2);
    TreeNode* node3 = createNode(3);
    TreeNode* node4 = createNode(4);
    TreeNode* node5 = createNode(5);

    // 手动构建二叉树
    root->left = node2;
    root->right = node3;
    node2->left = node4;
    node2->right = node5;

    // 打印树的层次遍历结果
    printf("树的层次遍历结果:\n");
    levelOrderTraversal(root);

    // 释放内存（省略具体实现）

    return 0;
}
